// Package day_03_linklist reverse_linklist
// @Title day_03_linklist
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/8/30 17:20
// @Create  2021/8/30 17:20
package day_03_linklist

// ReverseListNode 翻转一个链表 双指针 时间O(N) 空间 O(1)
func ReverseListNode(root *ListNode) *ListNode {
	if root == nil {
		return root
	}
	cur := root
	var pre *ListNode
	// 这个循环里面是最精髓的代码，多练习
	for cur != nil {
		temp := cur.Next
		cur.Next = pre
		pre = cur
		cur = temp
		// 下面写一个比较骚的版本 可读性不强，但是很骚
		// cur.Next, pre, cur = pre, cur, cur.Next
	}
	return pre
}

// ReverseListNode2 简单版本
func ReverseListNode2(root *ListNode) *ListNode {
	if root == nil {
		return root
	}
	cur := root
	var f, s *ListNode
	for cur != nil {
		f = cur.Next
		cur.Next = s // 移动指针指向
		s = cur      // 后指针前移动
		cur = f      // 当前指针后移动
	}
	return s
}

// ReverseListNodeStack 翻转一个链表 使用栈
func ReverseListNodeStack(root *ListNode) *ListNode {
	if root == nil {
		return root
	}
	// 创建一个栈
	var stack []*ListNode
	for root != nil {
		stack = append(stack, root)
		root = root.Next
	}
	var cur = new(ListNode)
	pre := cur
	for len(stack) > 0 {
		temp := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		cur.Next = temp
		cur = cur.Next
	}
	cur.Next = nil
	return pre.Next
}

// ReverseListNodeRecursion 翻转一个链表 使用递归 时间O(N) 空间 O(N)
func ReverseListNodeRecursion(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := ReverseListNodeRecursion(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
	//if root == nil {
	//	return root
	//}
	//var recursion = func(cur, pre *ListNode) *ListNode {
	//	return nil
	//}
	//recursion = func(cur, pre *ListNode) *ListNode {
	//	if cur == nil {
	//		return pre
	//	}
	//	res := recursion(cur.Next, cur)
	//	cur.Next = pre
	//	return res
	//}
	//return recursion(root, nil)
}
